import java.util.Arrays;

/**
 * 1365. 有多少小于当前数字的数字
 * https://leetcode-cn.com/problems/how-many-numbers-are-smaller-than-the-current-number/
 */
public class Solutions_1365 {
    public static void main(String[] args) {
        int[] nums = {8, 1, 2, 2, 3};  // output: {4, 0, 1, 1, 3}
//        int[] nums = {6, 5, 4, 8};  // output: {2, 1, 0, 3}
//        int[] nums = {7, 7, 7, 7};  // output: {0, 0, 0, 0}

        int[] result = smallerNumbersThanCurrent(nums);
        System.out.println(Arrays.toString(result));
    }

    /**
     * 解法三：哈希表计数法（1ms）
     * 题目限制了数值大小为 0 <= nums[i] <= 100，那么可以通过哈希数组来记录
     *             数组：0 1 2 3 4 5 6 7 8
     *        出现的次数：0 1 2 1 0 0 0 0 1
     * 小于等于的个数个数：0 1 3 4 4 4 4 4 5
     */
    public static int[] smallerNumbersThanCurrent(int[] nums) {
        int len = nums.length;
        int[] res = new int[len];
        // map[10] = 2，表示数值 10 在 nums 中出现 2 次
        int[] map = new int[101];
        for (int num : nums) {
            map[num] ++;
        }
        for (int i = 1; i < 101; i++) {
            // 从前往后累加出现次数，最终 map 记录的是小于等于 i 的元素个数，即绝对小于 i + 1 元素的个数
            map[i] += map[i - 1];
        }
        for (int i = 0; i < len; i++) {
            // 比数值 3 小的元素个数即是数值小于等于 2 的元素个数，即 map[3 - 1] = map[2]
            if (nums[i] > 0) {
                res[i] = map[nums[i] - 1];
            }
        }
        return res;
    }

    /**
     * 解法二：排序（6ms）
     */
    public static int[] smallerNumbersThanCurrent3(int[] nums) {
        int len = nums.length;
        // 将 nums 数组中的元素及索引，添加到二维数组中
        // newArr[0][0] = 10，newArr[0][1] = 2，表示原本 nums 数组中数值 10 在索引 2 位置上
        // 二维数组作用：保证数值元素排序后，索引不变
        int[][] newArr = new int[len][2];
        for (int i = 0; i < len; i++) {
            newArr[i][0] = nums[i];
            newArr[i][1] = i;
        }
        int[] res = new int[len];
        // 根据数值排序（升序）
        Arrays.sort(newArr, (o1, o2) -> o1[0] - o2[0]);

        for (int i = 1; i < len; i++) {
            int idx = newArr[i][1];
            if (newArr[i][0] == newArr[i - 1][0]) {
                // 与前一元素相等时，结果也与前一元素相同
                int before = newArr[i - 1][1];
                res[idx] = res[before];
            } else {
                // 比 nums[i] 小的元素有 i 个
                res[idx] = i;
            }
        }
        return res;
    }

    /**
     * 解法一：暴力法（20ms）
     */
    public static int[] smallerNumbersThanCurrent2(int[] nums) {
        int len = nums.length;
        int[] res = new int[len];
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                res[i] += nums[i] > nums[j] ? 1 : 0;
            }
        }
        return res;
    }
}
